package linklist;

import org.junit.Test;

import java.util.HashMap;
import java.util.TreeMap;

//随机链表的复制
public class LeetCode_138 {

    private class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        public Node(int val,Node next) {
            this.val = val;
            this.next = next;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        return solution_1(head);
    }

    @Test
    public void test(){
        Node node1=new Node(7);
        Node node2=new Node(13);
        Node node3=new Node(11);
        Node node4=new Node(10);
        Node node5=new Node(1);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=null;
        node1.random=null;
        node2.random=node1;
        node3.random=node5;
        node4.random=node3;
        node5.random=node1;
        Node head = node1;
        System.out.println(printRandomList(head));
        Node result = solution_2(head);
        System.out.println(printRandomList(result));
        System.out.println(printRandomList(head));

    }

    // 解法1：利用map存储克隆之后的节点位置,最后进行重构操作
    public Node solution_1(Node head) {
        Node temp = head;
        HashMap<Node, Node> map = new HashMap<>();
        //1. 复制
        while (temp!= null) {       //复制节点
            map.put(temp,new Node(temp.val));
            temp = temp.next;
        }
        //2. 重构
        temp = head;
        Node start = new Node(0),temp2=start;
        //2.1 添加next指针
        while(temp!=null){
            temp2.next=map.get(temp);
            temp=temp.next;
            temp2=temp2.next;
        }
        temp2.next=null;
        start=start.next;
        temp2=start;
        temp=head;
        //2.2 添加random指针
        while (temp!=null){
            if (temp.random!=null){
                temp2.random=map.get(temp.random);
            }else {
                temp2.random = null;
            }
            temp2=temp2.next;
            temp=temp.next;
        }
        return start;
    }

    // 解法2：每个节点后克隆一个相同的节点，在按照对节点处理，设置新节点的random指针，最后在将链表分离
    public Node solution_2(Node head) {
        //1. 节点复制
        Node temp1=head,temp2=null;
        while(temp1!=null){
            Node node = new Node(temp1.val);
            node.next=temp1.next;
            temp1.next=node;
            temp1= temp1.next.next;
        }
        //2. 逐对处理，random
        temp1=head;temp2=null;
        while(temp1!=null){
            if (temp1.random==null){        //节点的随机节点为空
                temp1.next.random=null;
            }else {                 //不为空
                temp1.next.random=temp1.random.next;
            }
            temp1= temp1.next.next;
        }

        //3. 逐对处理，next
        Node start=new Node(0);
        temp1=head;temp2=start;
        while(temp1!=null){
            //新链表
            temp2.next=temp1.next;
            temp2=temp2.next;

            //旧链表
            temp1.next=temp1.next.next;
            temp1= temp1.next;
        }
        temp2.next=null;


        return start.next;


    }

    public static String printRandomList(Node head) {
        String res = "";
        while (head!=null) {
            res += "["+head.val+","+((head.random!=null)?head.random.val:"null")+"]";
            head=head.next;
        }
        return null;
    }


}
